package org.basis.algorithm.promote;

import org.basis.algorithm.common.SortUtil;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 子数组个数
 *
 * @author Mr_wenpan@163.com 2022/03/16 21:50
 */
public class SubArrayCount {

    public static void main(String[] args) {
        int[] ints = {100, 200, 300};
        List<List<Integer>> subArrayList = subArrayList(ints);
        System.out.println("ints的所有子数组为" + subArrayList);
        int subArrayNums = subArrayNums(ints);
        System.out.println("ints的子数组个数为：" + subArrayNums);
        List<List<Integer>> allSubList = continuousSubList(ints);
        System.out.println("ints的所有连续子数组为：" + allSubList);
        int[] arr = {1, 1, 2};
        int res = subarrayBitwiseORs2(arr);
        System.out.println(res);

        test();
    }

    /**
     * 给定一个数组，求该数组的子数组个数
     * 该方法如果用数学方法求的话会非常简单
     */
    public static int subArrayNums(int[] nums) {
        // 非法参数
        if (nums == null) {
            return 0;
        }
        return nums(nums, 0);
    }

    /**
     * 对于每个位置都可以选择要或者不要（针对于当前位置的某一种抉择去获取他的子问题的解）
     */
    public static int nums(int[] nums, int index) {
        // 当决策完最后一个位置后，开始统计结果（得到一种子数组，所以返回1）
        if (index == nums.length) {
            return 1;
        }
        // 要
        int nums1 = nums(nums, index + 1);
        // 不要
        int nums2 = nums(nums, index + 1);
        return nums1 + nums2;
    }

    /**
     * 给你一个数组nums，求该数组的子数组集合
     *
     * @param nums 数组
     * @return List 子数组集合
     */
    public static List<List<Integer>> subArrayList(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return list;
        }
        // 递归决策
        process(nums, 0, new ArrayList<>(), list);
        return list;
    }

    /**
     * 求这种问题，对于每个位置都有两种选择，要或者不要
     *
     * @param nums           数组
     * @param index          当前来到的位置
     * @param decisionResult 每一个位置的决策结果存放集合
     * @param resultList     最终结果集
     */
    public static void process(int[] nums, int index, List<Integer> decisionResult, List<List<Integer>> resultList) {
        // 决策完数组最后一个位置后，将结果记录到resultList
        if (nums.length == index) {
            // 注意：Java中list是引用类型，所以这里需要将决策完的结果【拷贝一份】然后放入结果集
            List<Integer> copy = new ArrayList<>(decisionResult);
            resultList.add(copy);
            return;
        }

        // 对于每个位置都有两种选择，要或者不要，定了index位置后，然后去决策index + 1 位置
        // 1、要当前位置的数
        decisionResult.add(nums[index]);
        process(nums, index + 1, decisionResult, resultList);

        // 2、不要当前位置的数（这里注意要把上面add的数remove掉，注意这里是按照数组下标remove的）
        // 注意这里始终是remove的最后一个元素
        decisionResult.remove(decisionResult.size() - 1);
        process(nums, index + 1, decisionResult, resultList);
    }

    /**
     * 求arr的所有连续子数组
     */
    public static List<List<Integer>> continuousSubList(int[] arr) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (arr == null || arr.length < 1) {
            return resultList;
        }
        // 对于每个位置都求包含他本身在内的所有连续子数组
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                // 从 i ~ j位置求得一个子数组
                List<Integer> subList = new ArrayList<>();
                resultList.add(subList);
                for (int k = i; k <= j; k++) {
                    subList.add(arr[k]);
                }
            }
        }
        // 返回最终结果
        return resultList;
    }

    /**
     * 题目来源：https://leetcode-cn.com/problems/bitwise-ors-of-subarrays/comments/
     */
    public static int subarrayBitwiseORs2(int[] arr) {
        // 特殊情况特殊处理
        if (arr == null || arr.length < 1) {
            return 0;
        }

        // 利用hash表可以去重的特性
        HashSet<Integer> set = new HashSet<Integer>();
        int len = arr.length;
        // 使用双重循环来求得【所有连续子数组】
        for (int i = 0; i < len; i++) {
            // 0 和任意数进行或操作都等于他本身
            int orResult = 0;
            // 每一轮都可以求得：包含i位置的【所有的连续子数组】，对每个子数组都做或操作
            for (int j = i; j < len; j++) {
                orResult = (orResult | arr[j]);
                set.add(orResult);
            }
        }

        return set.size();
    }

    /**
     * 求arr的连续子数组的个数（解法1）
     */
    public static int subArrayCount(int[] arr) {
        if (arr == null) {
            return 0;
        }
        int count = 0;
        int len = arr.length;
        //对于每一个i位置都求一遍他有多少个子数组(这里可以通过数学方法计算即可)
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                count++;
            }
        }
        return count;
    }

    /**
     * 求arr的连续子数组的个数(解法2)
     */
    public static int subArrayCount2(int[] arr) {
        if (arr == null) {
            return 0;
        }
        int count = 0;
        int len = arr.length;
        //对于每一个i位置都求一遍他有多少个子数组
        for (int i = 0; i < len; i++) {
            count += (len - i);
        }
        return count;
    }

    public static void test() {
        for (int i = 0; i < 100; i++) {
            int[] array = SortUtil.generateRandomArray(100, 100);
            int count1 = subArrayCount(array);
            int count2 = subArrayCount2(array);
            if (count1 != count2) {
                System.out.println("error.");
            }
        }
    }
}
